package com.moter.demo01.niukeoffer.demo01;

/**
 * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 * 用例通过率: 100.00% 运行时间: 102ms 占用内存: 17320KB
 * 题解思路 ： 从左下角的元素m开始
 * 如果m=t,返回true
 * 如果m<t,m往右移一位，排除一列
 * 如果m>t,m往上移一位，排除一行
 * 性能比前两种提升了一倍 用时1295ms   运行1亿次
 * 二维长度n，一维长度m
 * 时间复杂度：O(n+m)
 * 空间复杂度：O(1)
 */
public class Solution03 {
    public static boolean Find(int target, int[][] array) {
        int m;
        for (int i = array.length - 1, j = 0; i >= 0 && j < array[i].length; ) {
            m = array[i][j];
            if (m == target)
                return true;
            else if (m < target)
                j++;
            else
                i--;
        }
        return false;
    }
    public static void main(String[] args) {//1295
        long start = System.currentTimeMillis();
        for (int i = 0; i < 100000000; i++) {
            Find(11, new int[][]{{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}});
        }
        System.out.println(System.currentTimeMillis() - start);
    }
}
